'''
树状数组。
区间 增值
单点 查询
@see c15_difference_array/difference_array.py
'''


class IndexTree():
    def __init__(self, size=32):
        # 差分数组
        self.difference_tree = [0] * (size + 1 + 1)
        self.N = size

    def _add(self, i, v):
        while i <= self.N:
            self.difference_tree[i] += v
            i += i & -i

    def add(self, l, r, v):
        self._add(l, v)
        self._add(r + 1, -v)

    def find(self, i):
        res = 0
        while i > 0:
            res += self.difference_tree[i]
            i -= i & -i
        return res
